package cn.xaut.动态规划;

/**
 * 978. 最长湍流子数组
 */
public class demo978 {

    // 动态规划
    public int maxTurbulenceSize(int[] arr) {

        int len = arr.length;
        if (len < 2)
            return len;

        int[] increased = new int[len];
        int[] decreased = new int[len];

        // 基础状态
        increased[0] = 1;
        decreased[0] = 1;

        int res = 1;
        for (int i = 1; i < len; i++) {

            // 状态转移
            if (arr[i - 1] < arr[i]) {
                increased[i] = decreased[i - 1] + 1;
                decreased[i] = 1;
            } else if (arr[i - 1] > arr[i]) {
                decreased[i] = increased[i - 1] + 1;
                increased[i] = 1;
            } else {
                increased[i] = 1;
                decreased[i] = 1;
            }

            res = Math.max(res, Math.max(increased[i], decreased[i]));
        }

        return res;
    }

    public static void main(String[] args) {

        System.out.println(new demo978().maxTurbulenceSize(new int[]{9, 4, 2, 10, 7, 8, 8, 1, 9})); // 5
        System.out.println(new demo978().maxTurbulenceSize(new int[]{4, 8, 12, 16}));   // 2
        System.out.println(new demo978().maxTurbulenceSize(new int[]{100}));    // 1
    }
}
